//
//  Problem1130.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/3.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit
/*
 1130. 叶值的最小代价生成树
 给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：

 每个节点都有 0 个或是 2 个子节点。
 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）
 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
 在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。
 
 示例：
     输入：arr = [6,2,4]
     输出：32
     解释：
     有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。

         24            24
        /  \          /  \
       12   4        6    8
      /  \               / \
     6    2             2   4
 
 提示：
     2 <= arr.length <= 40
     1 <= arr[i] <= 15
     答案保证是一个 32 位带符号整数，即小于 2^31。
 */
@objcMembers class Problem1130: NSObject {
    func solution() {
        
    }
    
    /*
     动态规划
     1: 创建一个数组dp[2][len]
     2: dp[i][0] 以i为左叶子节点的值
        dp[i][1] 0~i的最大值
     3: dp[i] = 2中情况：
        3.1 i只作为左叶子节点: arr[i] + dp[i+1]
        3.2 i作为左叶子节点，i+1作为右叶子节点
     */
    func mctFromLeafValues(_ arr: [Int]) -> Int {
        if arr.count == 2 {
            return arr[0] * arr[1]
        }
        
        var dp = Array(repeating: Array(repeating: -1, count: 2), count: arr.count)
        
        var minValue = arr[0]
        var i = 1
        while i < arr.count {
            let value = minValue * 1
            i += 1
        }
        
        return 0
    }
    
    func namemctFromLeafValuesDP(_ arr: [Int], _ dp: inout [[Int]], _ start: Int, _ minValue: Int) -> Int {
        if start > arr.count {
            return 0
        }
        if dp[start][0] != -1 {
            return dp[start][0]
        }
        
        // 自己作为左叶子节点
//        dp[start][0] =  arr[start] +  // dp[start - 1][1] * dp[]
        
        return dp[start][0]
    }
    
    func mctFromLeafValues1(_ arr: [Int]) -> Int {
        if arr.count == 2 {
            return arr[0] * arr[1]
        }
        
        var dp = Array(repeating: 0, count: arr.count)
        
        for i in 0..<arr.count {
            
        }
        
        return 0
    }
    func mctFromLeafValuesClearAlloc1(_ arr: [Int], _ dp: inout [Int], _ start: Int, _ value: Int, _ maxValue: inout Int) -> Int {
        if start == arr.count - 2 {
            let value = dp[start] * arr[start + 1]
            return maxValue + value
        }
        
        // 只作为左叶子节点
        var minValue = dp[start]
        var i = start + 1
        while i < arr.count {
            let value = minValue * 1
            i += 1
        }
        
        
        
        return 0
    }
    
}
